package com.zhupf.part7;

/**
 * @author zhupf
 * @date 2023年11月20日 10:20
 * @Description
 *
 *  25、K个一组反转链表
 */
public class ReverseKGroup {

    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        reverseKGroup2(head,2);
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre = new ListNode(0);
        ListNode tmp = pre;
        boolean flag = true;
        int i = 1 ;
        while (flag && head != null){
            ListNode t = head;
            while (i < k && head != null ){
                head = head.next;
                i ++;
            }
            if(!(flag = (i == k) ) || head == null){
                tmp.next = t;
                flag = false;
            }else {
                i = 1;
                ListNode t2 = head.next;
                head.next = null;
                head = t2;
                ListNode t3 = t;
                tmp.next = reverseNode(t);
                tmp = t3;
            }
        }
        return pre.next;
    }


    public static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode res = pre;
        ListNode start = pre;
        ListNode end = pre;
        while (true){
            for (int i = 0 ; i < k && end != null; i ++){
                end = end.next;
            }
            if(end == null){
                break;
            }
            start = start.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverseNode(start);
            start.next = next;
            end = start;
            pre = start;
        }
        return res.next;
    }

    private static ListNode reverseNode(ListNode head){
        ListNode p = null;
        while (head != null){
            ListNode t = head.next;
            head.next = p;
            p = head;
            head = t;
        }
        return p;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
